package com.company.tree;

import com.company.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author jrue
 * @version 1.0
 * @date 2020/1/27 21:16
 * https://leetcode-cn.com/problems/binary-tree-postorder-traversal/
 * 给定一个二叉树，返回它的 后序 遍历。
 */
public class BinaryTreePostorderTraversal {



    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        postorder(root,list);
        return list;
    }

    public List<Integer> postorderTraversal02(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) return list;
        Stack<TreeNode> stack01 = new Stack<>();
        Stack<TreeNode> stack02 = new Stack<>();

        stack01.push(root);

        while (!stack01.isEmpty()) {
            TreeNode node = stack01.pop();
            stack02.push(node);
            if (node.left != null) {
                stack01.push(node.left);
            }
            if (node.right != null) {
                stack01.push(node.right);
            }
        }

        while (!stack02.isEmpty()) {
            list.add(stack02.pop().val);
        }

        return list;
    }

    public void postorder(TreeNode root,List<Integer> list) {
        if (root == null) return;

        postorder(root.left,list);
        postorder(root.right,list);
        list.add(root.val);
    }
}
